/**
 * Created with IntelliJ IDEA.
 * Description:
 * 合并俩个有序链表
 * User: xwl
 */

class ListNode4 {
    int val;
    ListNode5 next;
    ListNode4() {}
    ListNode4(int val) { this.val = val; }
    ListNode4(int val, ListNode5 next) { this.val = val; this.next = next; }
}

public class Test6 {
    public ListNode5 mergeTwoLists(ListNode5 list1, ListNode5 list2) {
        // 定义一个新的头节点和一个暂存的节点
        ListNode5 newHead = new ListNode5();
        ListNode5 tmp = newHead;
        // 实现
        while (list1 != null && list2 != null) {
            if (list1.val < list2.val) {
                tmp.next = list1;
                tmp = list1;
                list1 = list1.next;
            }else {
                tmp.next = list2;
                tmp = list2;
                list2 = list2.next;
            }
        }
        // 判断剩余情况
        if (list1 != null) {
            tmp.next = list1;
        }
        if (list2 != null) {
            tmp.next = list2;
        }
        // 返回
        return newHead.next;
    }
}
